package com.wq.sort;

/**
 * @Author: wangqiang20995
 * @Date:2019/2/28
 * @Description:
 * @Resource:
 */
public class ChooseSort extends BaseSort {

    public ChooseSort(int size) {
        super(size);
    }


    public void sortCommon() {

        for (int i = 0; i < array.length - 1; i++) {//外层循环次数是个数-1，最后一个已经不需要排序了

            int minPosition = i;

            for (int j = i + 1; j <= array.length - 1; j++) {//从i+1开始与i比较，如果比i小就记下更小的数的position，直到结束
                if (array[j] < array[minPosition]) {
                    minPosition = j;
                }

            }

//            System.out.println("第" +i+"次循环，从i+1中找到最小的["+minPosition+"]数-->"+array[minPosition]);
            if (i != minPosition) {
                int temp = array[i];
                array[i] = array[minPosition];
                array[minPosition] = temp;
            }
        }
    }

    public void sortLowHigh(){
        int minPosition,maxPosition;

        for(int i = 0;i<array.length/2;i++){//不需要等于，即便array.length是奇数，那么最后一轮时，剩三个数，最大最小都已经到各自位子上了，那么中间这个就是已经不需要排序了
            minPosition = i;
            maxPosition = i;

            for(int j = i+1;j<array.length - 1 - i;j++){//排序了i轮，那么数组前i个和最后i个都不需要参与比较了
                if(array[j] < array[minPosition]){
                    minPosition = j;
                    continue;//既然这个时候是最小的了，那么就肯定不是最大的
                }

                if(array[j] > array[maxPosition]){
                    maxPosition = j;
                }
            }

            if(minPosition != i){

                int temp = array[i];
                array[i] = array[minPosition];
                array[minPosition] = temp;

                if(maxPosition == i){//这次遍历中，下标为i的刚好是最大的数，因为之前的位置为i的数已经去了minPosition，所以maxPosition需要更新过去
                    maxPosition = minPosition;
                }
            }

            if(maxPosition != array.length - 1 - i){
                int temp = array[array.length - 1 - i];
                array[array.length-1-i] = array[maxPosition];
                array[maxPosition] = temp;
            }
        }
    }

    public static void main(String args[]) {
        ChooseSort chooseSort = new ChooseSort(100000);
        chooseSort.printArray(true);
        System.out.println();
        long start = System.currentTimeMillis();
//        chooseSort.sortCommon();
        chooseSort.sortLowHigh();
        long end = System.currentTimeMillis();
        chooseSort.printArray(true);
        System.out.println();
        System.out.println("choose common cost:" + (end - start));
    }
}
